﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Tarjan
{
    class SCC
    {
        private int index;
        private Stack<Node> s;

        private List<List<Node>> components;
        private List<Node> currComponent;

        public SCC() {
            components = new List<List<Node>>();
        }

        public List<List<Node>> Tarjan(Graph g) {
            index = 0;
            s = new Stack<Node>();

            foreach(Node node in g.Nodes) {
                if(node.Index == -1) {
                    StrongConnect(node);
                }
            }

            return components;
        }

        private void StrongConnect(Node v) {
            v.Index = index;
            v.Lowlink = index;
            index++;
            s.Push(v);

            Node w;
            foreach(Edge e in v.OutgoingEdges) {
                w = e.To;

                if(e.To.Index == -1) {
                    StrongConnect(w);
                    v.Lowlink = Math.Min(v.Lowlink, w.Lowlink);
                } else if(s.Contains(e.To)) {
                    v.Lowlink = Math.Min(v.Lowlink, w.Index);
                }
            }

            if(v.Lowlink == v.Index) {
                currComponent = new List<Node>();
                do {
                    w = s.Pop();
                    currComponent.Add(w);
                } while(w != v);
                components.Add(currComponent);
            }
        }

        public void PrettyPrint() {
            foreach(List<Node> component in components) {
                Console.WriteLine("Component Size: " + component.Count);

                foreach(Node node in component) {
                    Console.WriteLine(string.Format("Node {0}", node.Id));
                }
                Console.WriteLine();
            }
        }
    }

    class Program
    {
        static void Main(string[] args) {
            Graph g = new Graph();
            g.Nodes = new List<Node> {
                new Node(1), new Node(2),
                new Node(3), new Node(4),
                new Node(5), new Node(6),
                new Node(7), new Node(8),
                new Node(9), new Node(10),
                new Node(11)
            };

            g.Nodes[0].OutgoingEdges.Add(new Edge { From = g.Nodes[0], To = g.Nodes[1] });      //1 -> 2
            g.Nodes[1].OutgoingEdges.Add(new Edge { From = g.Nodes[1], To = g.Nodes[2] });      //2 -> 3
            g.Nodes[2].OutgoingEdges.Add(new Edge { From = g.Nodes[2], To = g.Nodes[0] });      //3 -> 1
            g.Nodes[1].OutgoingEdges.Add(new Edge { From = g.Nodes[1], To = g.Nodes[10] });     //2 -> 11
            g.Nodes[2].OutgoingEdges.Add(new Edge { From = g.Nodes[2], To = g.Nodes[3] });      //3 -> 4
            g.Nodes[2].OutgoingEdges.Add(new Edge { From = g.Nodes[2], To = g.Nodes[6] });      //3 -> 7
            g.Nodes[3].OutgoingEdges.Add(new Edge { From = g.Nodes[3], To = g.Nodes[4] });      //4 -> 5
            g.Nodes[3].OutgoingEdges.Add(new Edge { From = g.Nodes[3], To = g.Nodes[5] });      //4 -> 6
            g.Nodes[3].OutgoingEdges.Add(new Edge { From = g.Nodes[3], To = g.Nodes[8] });      //4 -> 9
            g.Nodes[4].OutgoingEdges.Add(new Edge { From = g.Nodes[4], To = g.Nodes[5] });      //5 -> 6
            g.Nodes[4].OutgoingEdges.Add(new Edge { From = g.Nodes[4], To = g.Nodes[7] });      //5 -> 8
            g.Nodes[5].OutgoingEdges.Add(new Edge { From = g.Nodes[5], To = g.Nodes[6] });      //6 -> 7
            g.Nodes[6].OutgoingEdges.Add(new Edge { From = g.Nodes[6], To = g.Nodes[3] });      //7 -> 4
            g.Nodes[7].OutgoingEdges.Add(new Edge { From = g.Nodes[7], To = g.Nodes[8] });      //8 -> 9
            g.Nodes[8].OutgoingEdges.Add(new Edge { From = g.Nodes[8], To = g.Nodes[9] });      //9 -> 10
            g.Nodes[9].OutgoingEdges.Add(new Edge { From = g.Nodes[9], To = g.Nodes[7] });      //10 -> 8
            g.Nodes[10].OutgoingEdges.Add(new Edge { From = g.Nodes[10], To = g.Nodes[8] });    //11 -> 9
            g.Nodes[10].OutgoingEdges.Add(new Edge { From = g.Nodes[10], To = g.Nodes[9] });    //11 -> 10

            var scc = new SCC();
            scc.Tarjan(g);

            scc.PrettyPrint();
        }
    }

    class Graph
    {
        public List<Node> Nodes { get; set; }
    }

    class Node
    {
        private int id;
        private int index;
        private int lowlink;
        private List<Edge> outgoingEdges;

        public Node(int id) {
            this.id = id;

            index = -1;
            lowlink = -1;
            outgoingEdges = new List<Edge>();
        }

        public int Index {
            get { return index; }
            set { index = value; }
        }

        public int Lowlink {
            get { return lowlink; }
            set { lowlink = value; }
        }

        public List<Edge> OutgoingEdges { get { return outgoingEdges; } }

        public int Id {
            get { return id; }
        }
    }

    class Edge
    {
        public Node From { get; set; }
        public Node To { get; set; }
    }
}
